// 排序算法之冒泡排序

function ArrayList(){
  var array = [];

  this.insert = function(item){
    array.push(item);
  }

  this.toString = function(){
    return array.join()
  }

  // 冒泡排序
  this.bubbleSort = function(){
    var length = array.length;
    for(var i = 0; i < length; i++){
      for(var j = 0; j < length - 1; j++){
        if(array[j] > array[j+1]) {
          swap(j, j+1);
        }
      }
    }
  }

  var swap = function(index1, index2){
    var aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
  }

  // 改进后的冒泡排序 复杂度O(n2)
  this.modifiedBubbleSort = function(){
    var length = array.length;
    for(var i = 0; i < length - 1; i++){
      for(var j = 0; j < length - 1 - i; j++){
        if(array[j] > array[j + 1]){
          swap(j, j + 1);
        }
      }
    }
  }

  // 选择排序 O(n2)
  this.selectionSort = function(){
    var length = array.length,
        indexMin;
    for(var i = 0; i < length - 1; i++){
      indexMin = i;
      for(var j = i; j < length; j++){
        if(array[indexMin] > array[j]){
          indexMin = j;
        }
      }
      if(i !== indexMin){
        swap(i, indexMin);
      }
    }
  }

  // 插入排序
  // 排序小型数组时，此算法比选择排序和冒泡排序性能要好
  this.insertionSort = function(){
    var length = array.length,
        j, temp;
    for(var i = 1; i < length; i++){
      j = i;
      temp = array[i];
      while(j > 0 && array[j-1] > temp){
        array[j] = array[j-1];
        j--;
      }
      array[j] = temp;
    }
  }

  // 归并排序 复杂度 O(nlogn)
  // 归并排序是第一个可以被实际使用的排序算法
  this.mergeSort = function(){
    array = mergeSortRec(array);
  }

  /**
   * 归并排序是一种分治算法
   * 其思想是将原始数组切分成较小的数组
   * 直到每个小数组只有一个位置
   * 接着将小数组归并成较大的数组
   * 直到最后只有一个排序完毕的大数组
   */
  var mergeSortRec = function(array){
    var length = array.length;
    if(length === 1){
      return array;
    }
    var mid = Math.floor(length / 2),
        left = array.slice(0, mid),
        right = array.slice(mid, length);

    return merge(mergeSortRec(left), mergeSortRec(right));
  }

  var merge = function(left, right){
    var result = [],
        il = 0,
        ir = 0;

    while(il < left.length && ir < right.length){
      if(left[il] < right[ir]){
        result.push(left[il++]);
      } else {
        result.push(right[ir++]);
      }
    }

    while(il < length.length){
      result.push(left[il++]);
    }

    while(ir < right.length){
      result.push(right[ir++]);
    }

    return result;
  }


  // 快速排序
  // 快速排序也许是最常用的排序算法了
  // 它的复杂度为 O(nlogn)
  // 且它的性能通常比其他的复杂度为 O(nlogn) 的排序算法要好
  // 和归并算法一样，快速排序也使用分治的方法，
  // 将原始数组分为较小的数组(但它没有像归并排序那样将它们分割开)
  
  this.quickSort = function(){
    quick(array, 0, array.length - 1);
  }

  var quick = function(array, left, right){
    var index;

    if(array.length > 1){
      index = partition(array, left, right);

      if(left < index - 1){
        quick(array, left, index - 1);
      }
      if(index < right){
        quick(array, index, right);
      }
    }
  }

  var partition = function(array, left, right){
    var pivot = array[Math.floor((right+left) / 2)],
        i = left,
        j = right;
    while(i <= j){
      while(array[i] < pivot){
        i++;
      }
      while(array[j] > pivot){
        j--;
      }
      if(i <= j){
        swapQuickStort(array, i, j);
        i++;
        j--;
      }
    }
    return i;
  }

  var swapQuickStort = function (array, index1, index2) {
    var aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
  }


  // 搜索算法
  
  // 顺序搜索
  // 顺序或线性搜索是最基本的搜索算法
  // 它的机制是，将每一个数据结构中的元素和要找的元素做比较
  this.sequentialSearch = function(item) {
    for (var i = 0; i < array.length; i++) {
      if (item === array[i]) {
        return i;
      }
    }
    return -1;
  }

  // 二分搜索
  // 二分搜索算法和猜数字游戏类似
  // 这个算法要求被搜索的数据结构已排序
  this.binarySearch = function(item) {
    this.quickSort();

    var low = 0,
        high = array.length - 1,
        mid, element;

    while (low <= high) {
      mid = Math.floor((high + low) / 2);
      element = array[mid];
      if (element < item) {
        low = mid + 1;
      } else if (element > item) {
        high = mid - 1;
      } else {
        return mid;
      }
    }
    return -1;
  }

}

function createNonSortArray(size){
  var array = new ArrayList();

  for(var i = size; i > 0; i--){
    array.insert(i);
  }
  return array;
}
